package dullstack;

import java.util.LinkedList;

/**
 * 生成窗口最大值数组
 * p18
 *
 * @author 罗俊华
 * @date 2021/7/20 - 10:43 上午
 */
public class FindNearMinLeftAndRight {

    LinkedList<Integer> queue = new LinkedList<Integer>();

    public static final int WIDTH = 3;

    private int currentIndex = 0;

    private int[] array;

    public FindNearMinLeftAndRight(int[] array) {
        this.array = array;
    }

    public void rightMove(Integer i) {

        if (queue.isEmpty()) {
            queue.push(i);
            return;
        }


        if (i - WIDTH == queue.peek()) {
            // 当前队列头的下标已经过期，需要将其移除
            queue.removeFirst();
        }

        Integer peekLast = queue.peekLast();

        if (array[i] < array[peekLast]) {
            // 新增的元素，比对尾的元素还要小，所以将其添加到队列尾部
            queue.add(i);

        } else {
            // 新增的元素 >= 队尾的元素，现将其从队列尾部移除。
            // 一直直到有元素比它大
            queue.removeLast();
            this.rightMove(i);

        }


    }


    public static void main(String[] args) {
        FindNearMinLeftAndRight f = new FindNearMinLeftAndRight(new int[]{4, 3, 5, 4, 3, 3, 6, 7});

        for (f.currentIndex = 0; f.currentIndex < f.array.length; f.currentIndex++) {


            f.rightMove(f.currentIndex);

            if (f.currentIndex + 1 - WIDTH >= 0) {

                System.out.println(f.array[f.queue.peek()]);

            }

        }


    }


}
